package com.xmg.dataStructure.tree.heapSort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int arr[] = {4,6,8,5,9};
        heapsort(arr);
    }

    public static void heapsort(int[] arr){
        System.out.println("堆排序！");
        int temp = 0;
//        adjustHeap(arr,1,arr.length);
//        System.out.println("第一次："+ Arrays.toString(arr)); //4,9,8,5,6
//        adjustHeap(arr,0,arr.length);
//        System.out.println("第二次："+Arrays.toString(arr)); //9,6,8,5,4

        //最终代码
        //arr.length/2 - 1是最后一个非叶子节点的坐标
        //此循环将每个非叶子节点从下而上执行一遍，走完之后整颗树变为一个大顶堆
        for (int i = arr.length / 2 -1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        //此循环作用为将每轮生成的最大值放到数组最后，再将前面的元素进行一次大顶堆运算得到最大值
        //依次类推，最终得到有序数组
        for (int j = arr.length-1;j>0;j--){
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }

        System.out.println("数组="+Arrays.toString(arr));
    }

    /**
     * 将一个数组（二叉树），调整成一个大顶堆
     * 功能：完成将 i 对应的非叶子节点调整成大顶堆
     * @param arr 待调整的元素
     * @param i 非叶子节点在数组的位置
     * @param length    对多少个元素进行调整，length在逐渐减少
     */
    public static void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i]; //取出当前元素，保存在临时变量

        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if(k+1 < length && arr[k] < arr[k+1]){ //左子节点小于右子节点
                k++;    //k指向右子节点
            }
            if(arr[k] > temp){//子节点大于父节点，交换位置
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        //for循环结束时，已经将i为父节点的树的最大值放在了顶点
        arr[i] = temp;
    }
}
